package com.example.algorithm.LinkedListAlgorithm;

/**
 * 给定一个链表，删除链表的倒数第 n 个节点并返回头结点。
 * 例如:
 * 给定一个链表: 1->2->3->4->5, 并且 n = 2.
 * 当删除了倒数第二个节点后链表变成了 1->2->3->5.
 * @author ZMJ
 * @date 2020/3/23
 */
/*
思路:
据题意可知，题目给定链表以及n值，删除链表中倒数第n个结点。
遍历基本上是需要从表头开始遍历的，要想遍历一次就完成任务，即是说在遍历第一次的时候就能找到倒数第n个结点，
换句话说，当我遍历到倒数第n个结点时就应当停止遍历了，那么我该怎么知道我遍历到了倒数第n个结点呢？
此时就可以用快慢指针的方法。
都知道倒数倒数即是从表尾(NULL)往前数，倒数第n个即是从表尾往前数第n个，
换句话说，如果从某个结点往后数n个结点就达到NULL,那么这个结点就显然是倒数第n个结点了，
因此，算法思路也就有了：用慢指针指向遍历的当前结点，用快指针指向当前结点往后数的第n个结点，如果快指针指向了NULL，则在链表中删除慢指针指向的结点。
 */
public class LinkedDelReciprocalNNode {


    /**
     * 查询倒数第n个节点
     * Created by ZMJ on 2020/3/23.
     */
    public static Node findReciprocalNNode(Node head, int n) {
        if (null == head) {
            return null;
        }
        Node slow = head;
        Node fast = head;
        while (n -- > 0) {
            fast = fast.getNext();
        }
        if (fast == null) {
            return null;
        }
        // 遍历到尾部 fast先到尾部,slow和fast相差n个
        while (fast.getNext() != null) {
            slow = slow.getNext();
            fast = fast.getNext();
        }
        return slow.getNext();
    }



    public static void main(String[] args) {
        Node head = Node.createLinkedList(10);
        Node.printLinkedList(head);
        Node nNode = findReciprocalNNode(head, 2);
        System.out.println("nNode:" + nNode);
    }


    public void delReciprocalNNode(Node node) {
        // todo
        return;
    }
}
